package week_ten;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class MinimumIntervalToIncludeEachQuery_1851 {
    public int[] minInterval(int[][] intervals, int[] queries) {
        List<Event> events = new ArrayList<>();
        for (int[] interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            int len = right - left + 1;
            events.add(new Event(1, left, len));
            events.add(new Event(-1, right, len));
        }
        for (int i = 0; i < queries.length; i++) {
            events.add(new Event(0, queries[i], i));
        }

        int[] ans = new int[queries.length];

        events.sort((a, b) -> a.pos != b.pos ? a.pos - b.pos : b.type - a.type);

        TreeMap<Integer, Integer> map = new TreeMap();

        for (Event event : events) {
            if (event.type == 1) {
                int value = map.getOrDefault(event.length, 0);
                map.put(event.length, value + 1);
            } else if (event.type == -1) {
                int value = map.get(event.length);
                value -= 1;
                if (value == 0)
                    map.remove(event.length);
                else map.put(event.length, value);

            } else {
                int index = event.length;
                ans[index] = map.isEmpty() ? -1 : map.firstKey();
            }
        }
        return ans;

    }

    class Event {
        int pos;
        int length;
        int type;//1 产生 0 询问 -1 消失

        public Event(int ty, int po, int len) {
            type = ty;
            pos = po;
            length = len;
        }
    }
}
